package leetcode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-11-03 09:45
 **/
public class LeetCode113 {

    List<List<Integer>> list = new LinkedList<>();
    Deque<Integer> deque = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return list;
    }

    //深度优先遍历
    private void dfs(TreeNode node, int target) {
        //遍历到叶子节点直接返回
        if (node == null) {
            return;
        }
        deque.offer(node.val);
        target -= node.val;
        if (node.left == null && node.right == null && target == 0) {
            list.add(new LinkedList<>(deque));
        }
        dfs(node.left, target);
        dfs(node.right, target);
        deque.pollLast();
    }

}
